package string;

public class LeetCode_28 {
    public static void main(String[] args) {
        LeetCode_28 leet = new LeetCode_28();
        int i = leet.strStr("hello", "ll");
        System.out.println(i);
    }
    public int strStr(String haystack, String needle) {
        int[] next = nextGenerate(needle);
        int j = 0;
        int cur = 0;
        for (int i = 0; i < haystack.length(); ) {
            if(j == needle.length()){
                break;
            }
            if(j > 0 && haystack.charAt(i) != needle.charAt(j)){
                j = next[j - 1];
                cur = i;
            }else{
                if(haystack.charAt(i) == needle.charAt(j)) j++;
                i++;
            }
        }
        return haystack.length() - cur > needle.length() ? cur : -1;
    }
    public int[] nextGenerate(String modeStr){
        int[] next = new int[modeStr.length()];
        char[] modeCharArray = modeStr.toCharArray();
        int j = 0;
        for (int i = 1; i < modeCharArray.length; i++) {
            while (j > 0 && modeCharArray[j] != modeCharArray[i]){
                j = next[j - 1];
            }
            if(modeCharArray[j] == modeCharArray[i]) j++;
            next[i] = j;
        }
        return next;
    }
}
